本场链接Codeforces Round #591

闲话

又是很惨淡的一场VP.C题走错了就很无语,也不知道是什么意思.

A. CME

题目大意:给定一个$n$,找出三个正整数$a,b,c$使之三者之和等于$n$且满足$a+b+c=n$.如果不满足,你可以对$n$加任意多次,问你最少要给$n$加多少才能找出一组合法的$a,b,c$.只需输出次数,不需要输出$a,b,c$.
数据范围:
$1 \leq n \leq 10^9$

思路

显然两个方程并起来可以获得一个$c=n/2$的条件,那么剩下的由于说三者必须是正整数,那么贪心的使$a=1$,就此可以得到三个数的方程,最后看缺多少补多少即可.假如$n$是个奇数,则优先补一个$c$.如果$b$是$0$则补$b$.最后看整体差了多少.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		int a = 1,b = n / 2 - 1,c = n / 2;
		if(n & 1)	++c;
		int res = 0;
		if(b == 0)	++res,++b;
		res += abs(a + b - c);
		printf("%d\n",res);
    }
    return 0;
}

B. Strings Equalization

题目大意:给两个长度相同的字符串$s$和$t$.现在规定一种操作:在一个字符串里任选一个元素,将这个元素的相邻的另外一个元素直接变成他.这个操作即可以对$s$使用也可以对$t$使用,问是否能让两个字符串变成一样的.只需输出是否,不需要具体方案.
数据范围:
$1 \leq |s| \leq 100$

思路

显然可以把这个所谓的操作换成:将字符串整个变成一个他含有的元素.那么显然,只要两个字符串都有一个相同的元素出现过,那么结果就是对的,反之是错的.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    int T;cin >> T;
    while(T--)
    {
		string a,b;cin >> a >> b;
		set<char> sa;
		int n = a.size();
		for(int i = 0;i < n;++i)	sa.insert(a[i]);
    	int ok = 0;
    	for(int i = 0;i < n;++i)
    	{
    		if(sa.count(b[i]))	
    		{
    			cout << "YES\n";
    			ok = 1;
    			break;
    		}
    	}
    	if(!ok)	cout << "NO\n";
    }
    return 0;
}

C. Save the Nature

题目大意:有$n$张票要出售,可以任意选定出售的顺序.对于每个票售卖的过程中来说,如果他售出的当前位置是$a$的倍数,则可以收取$x\%$的利润,如果是$b$的倍数,则可以收取$y\%$的利润,如果同时都满足,则利润叠加,如果都不满足则没有利润.现给定一个目标值$k$,问最少卖几张票可以让利润达到$k$,或说明是无解的.只需输出至少几张票而不需要输出具体方案.
数据范围:
$1 \leq n \leq 2*10^5$
$100 \leq p_i \leq 10^9$且保证$p_i mod 100 = 0$
$1 \leq k \leq 10^{14}$

错解思路

这个题非常明显的是一个二分答案的框架.假设说至少卖出$x$张票就可以达到$k$的目标,那么再加任意多张票进去,显然利润绝对不会减少,只会增多,因此只要$x$张票满足,那么比$x$多的票就一定也满足,所以框架就比较容易确定了:$check(limit)$表示最多买limit张票的前提下,是否可以得到$k$的利润.如果可以则缩小范围,反之扩大范围.无解的时候说明一直在扩大范围,则让$r=n+1$,一直扩大最后就会得到$n+1$,表示无解.
再考虑$check$怎么写,一个比较直观的想法就是先对整个价格序列排序,而后给定两个指针分别从头和从胃尾去弹出元素:假如当前的总数已经达到了$a$或$b$的倍数,那么就让较大的$r$的位置的价格去赚利润,这样想当然的做法连样例都过不了.会错误的判断第二个样例是无解的.
这样做的错误原因在于,不一定是让价格高的去得到利润是最好的,有可能出现$y$比较大,而只让值较大的去跟$y$利润的情况结合而导致较早的达成了$k$的利润目标,从而错误地判断了二分的判据.
想到这里,又有一个坑:既然单纯地判断不行,那我加一个特殊的贪心规则,即我只让其中一个收取利润的时候移动右边,即较大的价格的指针,左边的随缘,收到就收到的话,也还是错的,这样打补丁的问题在于,较大值不一定会用完,而这样构造的方案,很可能说可以让其中一个较小值被没有用到的较大值替换,从而减少操作次数.而显然这样打补丁的方式根本不能解决这个问题.

正解思路

错解的问题在于根本不能贪心的从两边选择,这是思想出了问题.正确的做法应该是看买limit张票的时候,能不能确定所有的利润并计算.这样从整个集合上入手就可以解决掉这个问题.
如果对整个序列先做一个预处理,即$rp_i$表示在买了第$i$张票的时候,有多少的利润率,没有为$0$,有则累加.就可以避免上面所说的到底选了谁的问题.这样做就可以根本的避免选取谁的问题.那么在$check$的时候,先确定最多买多少张票,即limit张票,把1~limit张票的$rp$全抠出来,再进行排序,就可以确定我在1~limit张票这个区间里,依次从高到低获得的利润.在一开始就对$p$进行排序,使之从大到小排列,那么显然,利润率高的应该和价格高的配合,使利润最大.其他的和上面的思路没有什么差别.
注意防范爆int

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e5+7;
int p[N],x,y,a,b,n;
ll k,rp[N],ch[N];
bool check(int limit)
{
	ll res = 0;
	for(int i = 1;i <= limit;++i)	ch[i] = rp[i];
	sort(ch + 1,ch + limit + 1);reverse(ch + 1,ch + limit + 1);
	for(int i = 1;i <= limit;++i)	res += p[i] / 100 * ch[i];
	return res >= k;	
}

signed main()
{
    int T;scanf("%lld",&T);
    while(T--)
    {
		scanf("%lld",&n);
		for(int i = 1;i <= n;++i)	scanf("%lld",&p[i]),rp[i] = 0;
    	sort(p + 1,p + n + 1);reverse(p + 1,p + n + 1);
    	scanf("%lld%lld%lld%lld",&x,&a,&y,&b);
    	scanf("%lld",&k);
    	for(int i = 1;i <= n;++i)
    	{
    		if(i % a == 0)	rp[i] += x;
    		if(i % b == 0)	rp[i] += y;
    	}
    	int l = 1,r = n + 1;
    	while(l < r)
    	{
    		int mid = l + r >> 1;
    		if(check(mid))	r = mid;
    		else l = mid + 1;
    	}
    	if(l == n + 1)	puts("-1");
    	else printf("%lld\n",l);
    }
    return 0;
}

D. Sequence Sorting

题目大意:给定一个$n$个元素的序列,每次可以选其中的一个元素,将整个序列里所有与他相等的元素全部拉到开头或者结尾.问最少要多少次操作才能使整个序列变得不下降.只需输出操作次数,不需要具体方案.
数据范围:
$1 \leq n \leq 3*10^5$
$1 \leq a_i \leq n$

思路

这题乍看上去也是非常的牛逼.不过可以注意到整个序列应该是可以划分成两种元素的:一种是需要移动的,一种是不需要移动的.由于说答案就是要找最少操作次数,那么显然只要让不需要移动的元素越多,则操作次数也就随之越少.
不过就是思考到这里也还是会发现没什么想法.先确定一下整个答案的上界,上界比较明显是所有元素的个数,因为最差也就是把所有的元素全部丢到后面,使整个序列有序而已.假设现在已经求出了不需要动的元素的个数,则最终答案就是总数减掉不动的.一个比较显然的想法就是对于一个值的元素应该当成一个集合来考虑,如果存在这样一种情况:2222.......33333即2的所有元素都在3的前面,并且2是比3恰好小的,就可以通过把他们两个之间的元素抽掉,而不动他们两个,使他们两个是不动的.因此可以继续推广出这个题的结论:不动的元素个数就是找出一组元素的值连续上升且位置之间没有交集的子序列.如果有交集,则两者不可能是都不动的,因为出现了一方夹着一方的情况不把其中一个往外抽必然还是卡着的.所以有了这个条件进一步的可以想到,对于每个元素来说,维护他在原序列里最早出现的位置和最晚出现的位置就可以知道两者之间是否有交集了.之后再仿照$LCS$的递推,就可以顺利的解决掉本题.
注意元素必须是连续上升的,因此跟$LCS$实际上是有点不同的,这个连续的条件特别强,是可以递推的原因.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5+7;
int a[N],L[N],R[N],f[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		for(int i = 1;i <= n;++i)
		{
			if(!L[a[i]])	L[a[i]] = i;
			R[a[i]] = i;
		}
		sort(a + 1,a + n + 1);
		int fres = unique(a + 1,a + n + 1) - (a + 1),ures = 0;
		for(int i = 1;i <= fres;++i)
		{
			if(L[a[i]] > R[a[i - 1]])	f[a[i]] = f[a[i - 1]] + 1;
			else f[a[i]] = 1;
			ures = max(ures,f[a[i]]);
		}
		for(int i = 1;i <= fres;++i)	L[a[i]] = R[a[i]] = 0;
		printf("%d\n",fres - ures);
    }
    return 0;
}